package ljl.codetop300;

public class _287_find_dup {

  /**
   * 本来放弃了，一看官方题解，比我的解法傻逼十倍
   * 一提交，自己的过了
   */
  static class test {
    public int findDuplicate(int[] nums) {
      for (int i = 0; i < nums.length; i++) {
        while (nums[i] != i + 1) {
          if (nums[nums[i] - 1] == nums[i]) return nums[i];
          swap(nums, i, nums[i] - 1);
        }
      }
      return 0;
    }
    void swap(int[] nums, int i, int j) {
      if (i != j) {
        int t = nums[i]; nums[i] = nums[j]; nums[j] = t;
      }
    }
  }

  /**
   * 没想到吧 可以二分！
   */
  static class bisect {
    public int findDuplicate(int[] nums) {
      int n = nums.length;
      int l = 1, r = n - 1, ans = -1;
      while (l <= r) {
        int mid = (l + r) >> 1;
        int cnt = 0;
        for (int num : nums) {
          if (num <= mid) {
            cnt++;
          }
        }
        if (cnt <= mid) {
          l = mid + 1;
        } else {
          r = mid - 1;
          ans = mid;
        }
      }
      return ans;
    }
  }

  static class copy_bisect {
    public int findDuplicate(int[] nums) {
      int l = 0, r = nums.length;
      while (l < r) {
        int mid = (l + r) / 2;
        int count = 0;
        for (int num : nums) {
          if (num <= mid) count++;
        }
        if (count <= mid) l = mid + 1;
        else r = mid;
      }
      return l;
    }
  }

  /**
   * 傻逼解法
   */
  static class bit {
    public int findDuplicate(int[] nums) {
      int n = nums.length, ans = 0;
      int bit_max = 31;
      while (((n - 1) >> bit_max) == 0) {
        bit_max -= 1;
      }
      for (int bit = 0; bit <= bit_max; ++bit) {
        int x = 0, y = 0;
        for (int i = 0; i < n; ++i) {
          if ((nums[i] & (1 << bit)) != 0) {
            x += 1;
          }
          if (i >= 1 && ((i & (1 << bit)) != 0)) {
            y += 1;
          }
        }
        if (x > y) {
          ans |= 1 << bit;
        }
      }
      return ans;
    }
  }

  static class copybit {
    public int findDuplicate(int[] nums) {
      int n = nums.length;
      int res = 0;
      // 对于每一位
      for (int i = 0, l = 32 - Integer.numberOfLeadingZeros(n - 1); i < l; i++) {
        int x = 0;
        int y = 0;
        for (int j = 0; j < n; j++) {
          // 每个数
          if ((nums[j] & (1 << i)) != 0) {
            x++;
          }
          // 每个 j 但是不包括 0
          if (j > 0 && (j & (1 << i)) != 0) {
            y++;
          }
        }
        if (x > y) {
          res |= 1 << i;
        }
      }
      return res;
    }
  }

  static class linklist {
    public int findDuplicate(int[] nums) {
      int slow = 0, fast = 0;
      do {
        slow = nums[slow];
        fast = nums[nums[fast]];
      } while (slow != fast);
      slow = 0;
      while (slow != fast) {
        slow = nums[slow];
        fast = nums[fast];
      }
      return slow;
    }
  }

  static class copy_linklist {
    public int findDuplicate(int[] nums) {
      int slow = 0;
      int fast = 0;
      do {
        slow = nums[slow];
        fast = nums[nums[fast]];
      } while (slow != fast);
      slow = 0;
      while (slow != fast) {
        slow = nums[slow];
        fast = nums[fast];
      }
      return slow;
    }
  }
}
